import rlrandom
import random
import heapq

class RetryGeneration: pass

class LevelArray:
	def __init__(self, width, height, value):
		self.width, self.height = width, height
		self.data = []
		for i in range(self.width):
			yline = []
			for j in range(self.height):
				yline.append( value )
			self.data.append( yline )
	def setEdges(self, value):
		for i in range(self.width):
			self.data[i][0] = value
			self.data[i][self.height-1] = value
		for i in range(self.height):
			self.data[0][i] = value
			self.data[self.width-1][i] = value
	def valueList(self):
		return [ (self.data[x][y], x, y) for x in range(self.width) for y in range(self.height) ]
	def listWithValue(self, value ):
		return [ (x, y) for x in range(self.width) for y in range(self.height) if self.data[x][y] == value ]
	def randomWithValue(self, value ):
		return random.choice( self.listWithValue(value) )

class CompositePollock:
	def __init__(self, width, height, negatives = 4, negativeFillRatio = 0.15 ):
		self.floors = PollockGenerator(width, height, fillRatio = 1.0)
		self.walls = []
		for i in range(negatives):
			self.walls.append( PollockGenerator(width, height, fillRatio = negativeFillRatio ) )
	def isWall(self, x, y):
		if self.floors.isWall(x,y): return True
		for w in self.walls:
			if not w.isWall(x,y): return True
		return False

class PollockGenerator:
	def __init__(self, width, height, edgeAvoidance = 2, iterations = 1000, fillRatio = 1.0, minimumRadius = 3.0, radiusSpan = 8.0):
		self.data = LevelArray( width, height, 0 )
		i = 0
		for i in range( iterations ):
			x0 = random.randint( edgeAvoidance, width - 1 - edgeAvoidance )
			y0 = random.randint( edgeAvoidance, height - 1 - edgeAvoidance )
			r = random.random() * radiusSpan + minimumRadius
			s = random.random()
			self.ball( x0, y0, s, r )
			i += 1
		self.walls = LevelArray( width, height, True )
		q = self.data.valueList()
		heapq.heapify( q )
		n = int( width * height * fillRatio + 0.5 )
		for i in range(n):
			v, x, y = heapq.heappop( q )
			if x == 0 or y == 0 or (x+1) == self.data.width or (y+1) == self.data.height:
				break
			self.walls.data[x][y] = False
	def isWall(self, x, y):
		return self.walls.data[x][y]
	def ball(self, x0, y0, s, r):
		for x in range(self.data.width):
			for y in range(self.data.height):
				dx, dy = x-x0, y-y0
				if dx*dx + dy*dy <= r*r:
					self.data.data[x][y] -= s / (r*r)

class CompositeHOD:
	def __init__(self, width, height, cells = 50 ):
		self.walls = LevelArray( width, height, True )
		negative = True
		for i in range(cells):
			cellSize = int( random.random() * 100 + 50 + 0.5 )
			negative = not negative
			if negative:
				cellSize /= 2
			hod = HardnessOmnipresentDigger( width, height, digSize = cellSize )
			for x in range(width):
				for y in range(height):
					if not hod.isWall(x,y):
						if not negative and self.walls.data[x][y]:
							self.walls.data[x][y] = False
						elif negative and not self.walls.data[x][y]:
							self.walls.data[x][y] = True
	def isWall(self, x, y):
		return self.walls.data[x][y]
			

class HardnessOmnipresentDigger:
	def __init__(self, width, height, digSize = None):
		self.data = LevelArray( width, height, 2**32 )
		for x in range(1,width-1):
			for y in range(1,height-1):
				edgeness = min( x, y, width - 1 - x, height - 1 - y )
				edgePenalty = int( 32 * (0.5**edgeness) + 0.5 )
				self.data.data[x][y] = int( 0.5 + random.random() * 8 ) + 1
				self.data.data[x][y] += edgePenalty
		if digSize == None:
			digSize = ((width-2) * (height-2)) // 2
#		complexity = 3
#		for i in range(complexity):
#			ds = rlrandom.DiamondSquare( max(width,height) )
#			ds.generate()
#			ds.normalize()
#			for x in range(width):
#				for y in range(height):
#					edgeness = min( x, y, width - 1 - x, height - 1 - y )
#					self.data.data[x][y] += 2.0 * (0.5 ** edgeness)
#					self.data.data[x][y] += ds.data[x][y]
		l = self.data.valueList()
		v, x, y = min( l )
		x, y = random.choice( [ (x_,y_) for v_, x_, y_ in l if v_ == v ] )
		self.adjacents = set()
		self.opens = set()
		self.add( x, y )
		while len(self.opens) <= digSize:
			x, y = random.choice( list( self.adjacents ) )
			self.data.data[x][y] -= 1
			if self.data.data[x][y] <= 0:
				self.add( x,y )
	def isWall(self, x, y):	
		return not (x,y) in self.opens
	def add(self, x, y):
		self.opens.add( (x,y) )
		if (x,y) in self.adjacents:
			self.adjacents.remove( (x,y) )
		self.data.data[x][y] = 0
		for dx, dy in [ (dx,dy) for dx in (-1,0,1) for dy in (-1,0,1) if dx or dy ]:
			tx, ty = x + dx, y + dy
			if tx < 0 or tx >= self.data.width: continue
			if ty < 0 or ty >= self.data.height: continue
			self.adjacents.add( (tx, ty) )
		

		


class HardnessDigger:
	def __init__(self, width, height, hardnessComplexity = 9, edgeGeometricFalloff = 3.0, coverage = 0.5, stepSize = 0.05):
		self.width, self.height = width, height
		self.hardness = []
		dgCount = (self.width-2) * (self.height-2)
		dgCount = int( 0.5 + dgCount * coverage )
		assert dgCount > 0
		#self.walkDiagonals = walkDiagonals
		for i in range(self.width):
			yline = []
			for j in range(self.height):
				if i == 0 or j == 0 or (i+1) == self.width or (j+1) == self.height:
					yline.append( None )
				else:
					yline.append( 0 )
			self.hardness.append( yline )
		mx = None
		for i in range( hardnessComplexity ):
			ds = rlrandom.DiamondSquare( max(width,height) )
			ds.generate()
			ds.normalize()
			for x in range(self.width):
				for y in range(self.height):
					if self.hardness[x][y] != None:
						self.hardness[x][y] += ds.data[x][y]
						if mx == None or self.hardness[x][y] > mx:
							mx = self.hardness[x][y]
		g = 1.0 / edgeGeometricFalloff
		for x in range(self.width):
			for y in range(self.height):
				d = min( x, y, self.width - 1 - x, self.height - 1 - y )
				if self.hardness[x][y] != None:
					self.hardness[x][y] += mx * g**d
		values = [ (self.hardness[x][y],x,y) for x in range(self.width) for y in range(self.height) if self.hardness[x][y] != None ]
		values.sort()
		for i in range( dgCount ):
			m, x, y = values.pop(0)
			self.hardness[x][y] = 0
		#mn, self.x, self.y = values[0]
		#mx, maxx, maxy = values[-1]
		#self.stepSize = stepSize * mx
		#print mn, self.x, self.y
		#self.hardness[self.x][self.y] = 0
		#self.digsLeft = dgCount - 1
		#while self.digsLeft > 0:
		#	self.walk()
		#print self.hardness[0][0]
	def walk(self):
		dirs = [ (1,0), (0,1), (-1,0), (0,-1) ]
		if self.walkDiagonals:
			dirs += [ (1,1), (-1,1), (1,-1), (-1,-1) ]
		dx, dy = random.choice( dirs )
		nx, ny = self.x + dx, self.y + dy
		if self.hardness[nx][ny] == None:
			pass
		elif self.hardness[nx][ny] == 0:
			self.x, self.y = nx, ny
		else:
			self.hardness[nx][ny] -= self.stepSize
			self.hardness[nx][ny] = max( self.hardness[nx][ny], 0 )
			if self.hardness[nx][ny] == 0:
				self.digsLeft -= 1
	def isWall(self, x, y):
		return self.hardness[x][y] == None or self.hardness[x][y] > 0

